using System;
using System.Collections.Generic;

namespace SharpFastCGI.Internals
{
	/// <summary>
	/// Lightweight directionay.
	/// </summary>
	/// <remarks>
	/// Designed to be used with few elements. The implementation uses
	/// a linked-list.
	/// </remarks>
	internal class LightDictionary<TKey,TValue> : IDictionary<TKey,TValue>
	{
		// There is an overhead of about 8 bytes for objects.
		// If the object contains 8 bytes worth of data, about half the space is
		// lost. Consequently, an array of struct half full is as efficient,
		// but it may require long copies when it has to grow.
		
		// Complexity for linked-list, with n elements, and n lookups:
		// n² / 2
		// Complexity for sorted array, with n elements, and n lookups:
		// 2 * n * log(n) / log(2)
		//
		// n² / 2 > 2 * n * log(n) / log(2)
		// <=> n > 4 * log(n) / log(2)
		// <=> n / log(n) > 4 * log(2)
		// <=> exp(n / log(n)) > exp(4 * log(2))
		// <=> exp(n) - n > exp(4) + 2
		
		private class Slot
		{
			public KeyValuePair<TKey,TValue> Pair;
			public Slot Next;
		}
		
		private int mCount;
		private Slot mFirst;
		
		public int Count
		{
			get { return mCount; }
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		public ICollection<TKey> Keys
		{
			get { throw new NotImplementedException(); }
		}

		public ICollection<TValue> Values
		{
			get { throw new NotImplementedException(); }
		}

		public TValue this[TKey Key]
		{
			get
			{
				Slot cur = mFirst;
				while(cur != null)
				{
					if(cur.Pair.Key.Equals(Key)) return cur.Pair.Value;
					cur = cur.Next;
				}
				throw new KeyNotFoundException();
			}
			set
			{
				Slot cur = mFirst;
				while(cur != null)
				{
					if(cur.Pair.Key.Equals(Key))
					{
						cur.Pair = new KeyValuePair<TKey,TValue>(Key, value);
						return;
					}
					cur = cur.Next;
				}
				AddWithoutCheck(new KeyValuePair<TKey,TValue>(Key, value));
			}
		}
		
		public LightDictionary()
		{
			mCount = 0;
			mFirst = null;
		}
		
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		public IEnumerator<KeyValuePair<TKey,TValue>> GetEnumerator()
		{
			Slot cur = mFirst;
			while(cur != null)
			{
				yield return cur.Pair;
				cur = cur.Next;
			}
		}
		
		public void AddWithoutCheck(KeyValuePair<TKey,TValue> Item)
		{
			Slot s = new Slot();
			s.Pair = Item;
			s.Next = this.mFirst;
			mFirst = s;
			++mCount;
		}
		
		public void Add(TKey Key, TValue Value)
		{
			if(ContainsKey(Key))
				throw new ArgumentException();
			else
				AddWithoutCheck(new KeyValuePair<TKey,TValue>(Key, Value));
		}
		
		public void Add(KeyValuePair<TKey,TValue> Item)
		{
			if(ContainsKey(Item.Key))
				throw new ArgumentException();
			else
				AddWithoutCheck(Item);
		}

		public void Clear()
		{
			mFirst = null;
			mCount = 0;
		}

		public bool Contains(KeyValuePair<TKey,TValue> Item)
		{
			Slot cur = mFirst;
			while(cur != null)
			{
				if(cur.Pair.Equals(Item)) return true;
				cur = cur.Next;
			}
			return false;
		}

		public bool ContainsKey(TKey Key)
		{
			Slot cur = mFirst;
			while(cur != null)
			{
				if(cur.Pair.Key.Equals(Key)) return true;
				cur = cur.Next;
			}
			return false;
		}
		
		public bool TryGetValue(TKey Key, out TValue Value)
		{
			Slot cur = mFirst;
			while(cur != null)
			{
				if(cur.Pair.Key.Equals(Key))
				{
					Value = cur.Pair.Value;
					return true;
				}
				cur = cur.Next;
			}
			
			Value = default(TValue);
			return false;
		}

		public void CopyTo(KeyValuePair<TKey,TValue>[] Array, int Offset)
		{
			Slot cur = mFirst;
			while(cur != null)
			{
				Array[Offset++] = cur.Pair;
				cur = cur.Next;
			}
		}

		public bool Remove(KeyValuePair<TKey,TValue> Item)
		{
			Slot prev = null, cur = mFirst;
			while(cur != null)
			{
				if(cur.Pair.Equals(Item))
				{
					if(prev == null)
						mFirst = cur.Next;
					else
						prev.Next = cur.Next;
					
					return true;
				}
				prev = cur;
				cur = cur.Next;
			}
			return false;
		}
		
		public bool Remove(TKey Key)
		{
			Slot prev = null, cur = mFirst;
			while(cur != null)
			{
				if(cur.Pair.Key.Equals(Key))
				{
					if(prev == null)
						mFirst = cur.Next;
					else
						prev.Next = cur.Next;
					
					return true;
				}
				prev = cur;
				cur = cur.Next;
			}
			return false;
		}
	}
}
